package leetcode.editor.cn;

public class _23_MergeKSortedLists {
    public static void main(String[] args) {
        Solution solution = new _23_MergeKSortedLists().new Solution();
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)


    class Solution {
        private ListNode mergeTwoList(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            if (l1.val < l2.val) {
                l1.next = mergeTwoList(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoList(l1, l2.next);
                return l2;
            }
        }

        private ListNode mergeKLists(ListNode[] lists, int start, int end) {
            if (start == end) {
                return lists[start];
            }
            return mergeTwoList(mergeKLists(lists, start, (start + end) / 2), mergeKLists(lists, (start + end) / 2 + 1, end));

        }

        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) {
                return null;
            }
            return mergeKLists(lists, 0, lists.length - 1);  // start 是数组的起始下标, end 是数组的结束下标, 左闭右闭
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}